/*
 * sizeBalancedTree.h
 * This file is part of Jamming
 *
 * Copyright (C) 2012 - Yi
 *
 * Jamming is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * Jamming is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Jamming. If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef __SIZEBALANCETREE_H__
#define __SIZEBALANCETREE_H__
#include <stack>
#include <string.h>

namespace Tree
{
    template <typename _TypeData>
    class sizeBalancedTree {
        /*
         * sizeBalancedTree is a variance of AVL tree. Instead of 
         * keeping the information of tree depth,it keeps the information of tree size.
         * It thus can be used to find kth element.
         */
        struct Node {
            int size;
            int child[2];
            _TypeData data;
        };
        Node* mytree;
        int size,max_size;
        static const int LEFT=0,RIGHT=1,Null=0;
        int idxInt;
        stack<int> deletedspace;
        //Internal memory management
        int newNode(_TypeData &data) {
            int idx;
            if(!deletedspace.empty()) {idx=deletedspace.top();deletedspace.pop();} 
            else {
                if(++size > max_size) resize(2*max_size);
                idx=size;
            }
#ifdef USE_MEMCPY
            memcpy(&mytree[idx].data,&data,sizeof(_TypeData));
#else
            mytree[idx].data=data;
#endif
            mytree[idx].child[LEFT]=mytree.child[RIHGT]=Null;
            return idx;
        };
        void deleteNode(int idx) {
            deletedspace.push(idx);
        };
        void resize(int newSize) {
            Node* newBuffer=new Node[newSize+1];
            if (!mytree) { 
                memcpy(newBuffer,mytree,(max_size+1)*sizeof(Node));
                delete mytree [];
            }
            max_size=newSize;
            mytree=newBuffer;
        };
        //Tree maintainance
        inline void rotate(int &idxOldRoot,int right) {
            int idxNewRoot=mytree[idxOldRoot].child[right];
            mytree[idxOldRoot].child[right]=mytree[idxNewRoot].child[!right];
            mytree[idxNewRoot].child[!right]=idxOldRoot;
            mytree[idxNewRoot].size=mytree[idxOldRoot].size;
            mytree[idxOldRoot].size=mytree[mytree[idxOldRoot].child[LEFT]].size+mytree[mytree[idxOldRoot].child[RIGHT]].size+1;
            idxOldRoot=idxNewRoot;
        };
        maintain(int &idxSubTree,bool isRight) {
            if(mytree[mytree[mytree[idxSubTree].child[isRight]].child[isRight]].size >mytree[mytree[idxSubTree].child[!isRight]].size) {
                rotate(idxSubTree,isRight);
            } else if(mytree[mytree[mytree[idxSubTree].child[isRight]].child[!isRight]].size > mytree[mytree[idxSubTree].child[isLeft]].size ) {
                rotate(idxSubTree,isRight);
                rotate(idxSubTree,isRight);
            } else return;
            maintain(mytree[idxSubTree].child[LEFT],LEFT);
            maintain(mytree[idxSubTree].child[RIGHT],RIGHT);
            maintain(idxSubTree,LEFT);
            maintain(idxSubTree,RIGHT);
        }
        //Tree operation
        bool insertTosubtree(Node* &node,_TypeData data) {
            if(!node) {
                int idx=newNode();
            }
        };
        bool removeFromsubtree(Node* &node,_TypeData data) {
            
        };
        public:
        sizeBalancedTree(int reserve_size=10) {
            resize(reserve_size);
            mytree[Null].child[LEFT]=mytree[Null].child[RIGHT]=Null;
        }
        insert();
        remove();
        find();
        bound(const _TypeData &data,int &idxBound[]) {
            int idxCurrNode=root;
            while(idxCurrNode) {
                int isRight=data > mytree[idxCurrNode].data;
                int isEqual=data == mytree[idxCurrNode].data;
                if(!isEqual) {
                    idxBound[isRight]=idxCurrNode;
                    idxCurrNode=mytree[idxCurrNode].child[isRight];
                }
            }
        }; 
        int rank(int idxNode) {
            int idxCurrNode=root;
            int rank=mytree[root].size+1;
            while(idxCurrNode) {
                int isRight=mytree[idxNode].data > mytree[idxCurrNode].data;
                int isEqual=mytree[idxNode].data == mytree[idxCurrNode].data;
                if(!isEqual) {idxCurrNode=mytree[idxCurrNode].child[isRight];
                    rank+=(mytree[mytree[idxCurrNode].child[!isRight]].size+1)*(isRight?1:-1);
                }
            }
            //not found in the tree
        };
        _TypeData select(int k) {
            int idxCurrNode=root;
            while(idxCurrNode) {
                int leftSize=mytree[mytree[idxCurrNode].child[LEFT]].size;
                if(k==leftSize+1) {return mytree[idxCurrNode].data}
                if(k>leftSize+1) {idxCurrNode=mytree[mytree[idxCurrNode].child[RIGHT]];k-=leftSize+1;}
                else {idxCurrNode=mytree[mytree[idxCurrNode].child[LEFT]];} 
            }
            //k> size , raise error;
        };
    };
};


#endif /* __SIZEBALANCETREE_H__ */

